#ifndef L4_D202412_H
#define L4_D202412_H
#include <cmath>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

/** Q1 兔子不吃窝边草
 *
 * 输入：
 * 兔子只能朝一个方向跳，同样多的草，兔子更喜欢向左和离得近的草跳
 * 1. n 草皮数量，i 兔子吃的第一块草皮编号（起始位置）
 * 2. n 块草坪皮，数值代表含草量，从左到右编号为 1~n
 *
 * 输出：
 * 1. 兔子最多能吃掉的草量
 * 2. 按兔子吃草顺序的草皮编号
 *
 * 解题思路：递归
 */

// Q1 答案结构体
struct res1 {
  int maxGrass;  // 最大吃草量
  int count;     // 草皮数量（路径 path 长度，用于最终结果 for 输出）
  int* path;     // 吃草路径
};

res1 resolve1(int grass[], int len) {
  res1 res;
  if (len < 1) {
    res = {0, 0, {0}};
  } else if (len == 1) {
    int path[1] = {1};
    res = {grass[0], 1, path};
  } else {
    res1 temp;
    // 吃第一块
    int pathE[len / 2] = {1};
    res1 eat = {grass[0], 1, pathE};
    temp = resolve1(&grass[2], len - 2);
    eat.maxGrass += temp.maxGrass;
    eat.count += temp.count;
    for (int i = 0; i < temp.count; i++) {
      eat.path[i + 1] = temp.path[i] + 2;
    }
    // 不吃第一块
    int pathN[len / 2] = {0};
    res1 neat = {0, 0, pathN};
    temp = resolve1(&grass[1], len - 1);
    neat.maxGrass += temp.maxGrass;
    neat.count += temp.count;
    for (int i = 0; i < temp.count; i++) {
      neat.path[i] = temp.path[i] + 1;
    }
    res = eat.maxGrass >= neat.maxGrass ? eat : neat;
  }
  return res;
}

int Q1() {
  // 输入测试数据
  int N, I;
  cin >> N >> I;
  int grass[N];
  for (int j = 0; j < N; j++) {
    cin >> grass[j];
  }
  // 1 2 3 4 5 6 7
  int lenL = I - 2, lenR = N - I - 1;          // 左右数组长度
  int grassL[lenL] = {0}, grassR[lenR] = {0};  // 初始化左右数组
  int startL = I - 3, startR = I + 1;          // 左右数组起始位置
  // 填充左右数组
  for (int j = 0; j < lenL; j++) {
    grassL[j] = grass[startL - j];
  }
  for (int j = 0; j < lenR; j++) {
    grassR[j] = grass[startR + j];
  }

  // 向左吃
  res1 left = resolve1(grassL, lenL);
  // 向右吃
  res1 right = resolve1(grassR, lenR);
  // 记录结果
  int path[N / 2] = {I};
  res1 res = {grass[I - 1], 1, path};
  // 哪个方向吃得多选哪个方向，一样则向左
  if (left.maxGrass >= right.maxGrass) {
    res.count += left.count;
    res.maxGrass += left.maxGrass;
    for (int j = 0; j < left.count; j++) {
      res.path[j + 1] = I - 1 - left.path[j];
    }
  } else {
    res.count += right.count;
    res.maxGrass += right.maxGrass;
    for (int j = 0; j < right.count; j++) {
      res.path[j + 1] = I + 1 + right.path[j];
    }
  }
  // 输出结果
  cout << res.maxGrass << "\n";
  for (int j = 0; j < res.count - 1; j++) {
    cout << res.path[j] << " ";
  }
  cout << res.path[res.count - 1];
}

/** Q2 漂亮的序列
 *
 * 输入：
 * 1. n 正整数个数，m 漂亮参数 (2 <= n <= 10^5, 1 <= m <= 10^3)
 * 2. n 个正整数 a[n] (1 <= a[i] <= 10^5)
 *
 * 输出：漂亮子序列个数（满足至少存在一对相邻 a - b <= m 的数列）
 *
 * 解题思路：逆向思维
 * 1. 找不漂亮的序列：所有相邻的数差值都大于 m 假设有 k 个
 * 2. 总共有 2^n - n - 1 种序列
 * 3. 找漂亮序列：2^n - n - 1 - k
 */

void Q2() {
  long long MOD = 1000000007;
  // (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10³)
  int n, m;
  cin >> n >> m;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  long long all = pow(2, n) - n - 1, k = 0, dp[n] = {0};
  // 找到所有不漂亮的数列
  // dp[1]=
  for (int i = 2; i < n; i++) {
  }
  cout << (all - k) % MOD << endl;
}

/** Q3 园林修整
 *
 * 输入：
 *
 * 输出：
 *
 * 解题思路：
 *
 */
void Q3() {}

/** Q4 字母游戏
 *
 * 输入：
 *
 * 输出：
 *
 * 解题思路：
 *
 */
void Q4() {
  string s, t;
  cin >> s >> t;
}

#endif